package arithmetic2.day02;

import java.util.Arrays;

/*
    快速排序
 */
public class Demo03 {
    public static void main(String[] args) {
        int arr[] = new int[]{3,6,8,3,1,2,0};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int arr[],int start,int end){
        if(start < end){
            //从数组中随机选择一个数来当做划分标准
            int key = arr[start+(int)(Math.random()*(end-start+1))];
            //划分
            int p[] = partition(arr,start,end,key);
            //左边排序
            quickSort(arr,start,p[0]);
            //右边排序
            quickSort(arr,p[1],end);
        }
    }

    //将数组划分为三段,左边全是小于某个数的，中间是等于某个数的，右边全是大于某个数的
    public static int[] partition(int arr[],int start,int end,int key){
        int i = start-1;  //小于等区域的最大索引,左边索引的数都是小于key的
        int j = end+1; //大于区域的最小索引，右边的数都是大于key的
        //遍历当前数组
        for(int k=start;k<=end && j>k;k++){
            if(arr[k]<key){    //当前数<key，将当前数与小于等于区域的下一个数交换，小于区域右扩1个 k++
                swap(arr,k,i+1);
                i++;
            }else if(arr[k]>key){  //当前数>key 将当前数与大于区的前一个数交换，大于区左扩,k不变
                swap(arr,k,j-1);
                j--;
                k--;
            }
        }
        return new int[]{i,j};
    }

    //交换两个数
    public static void swap(int arr[],int i,int j){
        int temp =  arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
